package week_five;

public class CapacityToShipPackagesInDdays_1011 {
    public int shipWithinDays(int[] weights, int days) {
        int l = 1, r = 25000000;
        while (l < r) {
            int mid = (l + r) / 2;
            if (isValidWeight(weights, days, mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    private boolean isValidWeight(int[] weights, int days, int w) {
        int dayCount = 1;
        int currWeight = 0;
        for (int i = 0; i < weights.length; i++) {
            if ((currWeight + weights[i]) <= w) {
                currWeight += weights[i];
            } else {
                if (w < weights[i]) return false;
                currWeight = weights[i];
                dayCount++;
            }
        }
        // System.out.println("mid is: "+ w +", days: "+ dayCount);
        return days >= dayCount;
    }
}
